package DoblePointer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

// *Definition for an interval.

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    @Override
    public String toString() {
        return "Interval{" +
                "start=" + start +
                ", end=" + end +
                '}';
    }
}

class Merge {
    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        //首先按照每个区间的左边界递增进行排序
        //几种情况，每次前后两个区间
        //(x,y) (i,j)
        //如果 i>y 则这是两个区间,不用合并;
        //如果y>j, 直接合并为 x,y;
        //如果 y>i && y<j 则合并为(x,j);


        //特例判断
        if (intervals.size() < 2) {
            return intervals;
        }
        //根据左边界和右边界排序
        Collections.sort(intervals, (o1, o2) -> o1.start - o2.start);
//         Collections.sort(intervals,(o1,o2)->o1.end-o2.end);
        //结果集
        ArrayList<Interval> res = new ArrayList<>();
        //利用辅助栈
        Stack<Interval> stack = new Stack<>();
        stack.push(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (stack.empty()) {
                stack.push(curr);
                continue;
            }
            Interval in = stack.pop();  //弹出最上面的

            //第二种情况
            if (in.end > curr.end) {
                stack.push(in);
            } else if (curr.start > in.end) {
                //第一种情况
                stack.push(in);
                stack.push(curr);
            } else if (in.end > curr.start && in.end < curr.end) {
                //第三种情况
                in.end = curr.end;
                stack.push(in);
            }
        }
        if (stack.empty()) {
            return res;
        } else {
            while (!stack.empty()) {
                res.add(stack.pop());
            }
        }
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        Interval interval1 = new Interval(10,30);
        Interval interval2 = new Interval(20,60);
        Interval interval3 = new Interval(80,100);
        Interval interval4 = new Interval(150,180);
        ArrayList<Interval> intervals = new ArrayList<>();
        intervals.add(interval4);
        intervals.add(interval3);
        intervals.add(interval2);
        intervals.add(interval1);
        System.out.println(Merge.merge(intervals));
    }
}

